

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 62536
 * Date: 2024-02-22
 * Time: 8:55
 */
public class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode(int val) {
        this.val = val;
    }

    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }

    //通过前序遍历和中序遍历创建二叉树
    //输入: preorder = [3,9,20,15,7], inorder = [9,3,15,20,7]
    //输出: [3,9,20,null,null,15,7]

    public int preIndex;
    public TreeNode buildTree(int[] preorder, int[] inorder) {

        return buildTreeChild(preorder, inorder, 0, inorder.length - 1);
    }
    private TreeNode buildTreeChild(int[] preorder, int[] inorder, int inBegin, int inEnd){
        if(inBegin > inEnd){
            return null;
        }

        TreeNode root = new TreeNode(preorder[preIndex]);

        int rootIndex = findRootIndex(inorder, inBegin, inEnd, preorder[preIndex]);
        preIndex++;
        root.left = buildTreeChild(preorder,inorder,inBegin, rootIndex-1);
        root.right = buildTreeChild(preorder,inorder,rootIndex+1, inEnd);

        return root;

    }

    private int findRootIndex(int[] inorder, int inBegin, int inEnd, int key) {
        for(int i = inBegin; i <= inEnd; i++) {
            if(inorder[i] == key) {
                return i;
            }
        }
        return -1;
    }
//    public  int preIndex ;
//    public TreeNode buildTree(int[] preorder, int[] inorder) {
//        return buildTreeChild(preorder,inorder,0,inorder.length-1);
//    }
//
//    private TreeNode buildTreeChild(int[] preorder, int[] inorder,int inBegin,int inEnd) {
//        if(inBegin > inEnd) {
//            return null;
//        }
//
//        TreeNode root =  new TreeNode(preorder[preIndex]);
//        int rootIndex = findRootIndex(inorder,inBegin,inEnd,preorder[preIndex]);
//        preIndex++;
//        root.left = buildTreeChild(preorder,inorder,inBegin,rootIndex-1);
//        root.right = buildTreeChild(preorder,inorder,rootIndex+1,inEnd);
//        return root;
//    }
//
//    private int findRootIndex(int[] inorder,int inBegin,int inEnd,int key) {
//        for(int i = inBegin; i <= inEnd;i++) {
//            if(inorder[i] == key) {
//                return i;
//            }
//        }
//        return -1;
//    }


    //判断对称二叉树
    public boolean isSymmetric(TreeNode root) {
        if(root == null) {
            return true;
        }
        return isSymmetricChild(root.left, root.right);

    }
    public boolean isSymmetricChild(TreeNode leftTree, TreeNode rightTree) {
        if(leftTree == null && rightTree == null) {
            return true;
        } else if (leftTree == null || rightTree == null) {
            return false;
        }
        if(leftTree.val != rightTree.val) {
            return false;
        }

        return isSymmetricChild(leftTree.left, rightTree.right) &&
                isSymmetricChild(leftTree.right, rightTree.left);

    }

    //判断一棵树是否为平衡二叉树
    public boolean isBalanced(TreeNode root) {
        if(root == null) {
            return true;
        }
        int leftH = getHeight(root.left);
        int rightH = getHeight(root.right);
        return Math.abs(leftH - rightH) < 2 && isBalanced(root.left) && isBalanced(root.right);
    }


    //获取树的高度
    public int getHeight(TreeNode root) {
        if (root == null) return 0;
        int leftH = getHeight(root.left);
        int rightH = getHeight(root.right);
        return leftH > rightH ? leftH + 1 : rightH + 1;
    }

}
